1309. Блоки строки

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с ее префиксом. Длину блока в позиции 0 будем считать равной нулю.

Вычислите длины блоков строки S для всех позиций.

Вход. Одна строка S (|S| ≤ 10⁶).

Выход. В одной строке выведите длины блоков строки S для всех позиций.

Пример входа	Пример выхода
abaabaab	0 0 1 5 0 1 2 0

РЕШЕНИЕ

строки – z-функция

Анализ алгоритма

Построим для строки S z-функцию и сохраним ее значения в массиве v. Выведем значения z-функции для всех позиций i (0 ≤ i < n).

Реализация алгоритма

Входная строка s содержит не более 10⁶ символов. z-функцию строки s сохраняем в векторе v.

vector<int> v;

string s;

Функция z строит и возвращает z-функцию для строки s.

vector<int> z(string s)

{

int i, l, r, len = s.size();

vector<int> z(len, 0);

l = 0, r = 0;

for (i = 1; i < len; i++)

{

if (i <= r) z[i] = min(r - i + 1, z[i - l]);

while (i + z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;

if (i + z[i] - 1 > r)

{

l = i;

r = i + z[i] - 1;

}

}

return z;

}

Основная часть программы. Читаем входную строку s.

getline(cin,s);

Вычисляем z-функцию.

v = z(s);

Выводим значения z-функции для всех позиций входной строки.

for (i = 0; i < v.size(); i++)

printf("%d ", v[i]);

printf("\n");